from typing import *


class Solution:

    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        nexts = [[] for _ in range(n)]
        for i, g in enumerate(graph):
            for v in g:
                nexts[i].append(v)

        br = [None] * n

        def f(i, r):
            if br[i] == r:
                return True
            if br[i] is not None:
                return False
            br[i] = r
            for next in nexts[i]:
                if not f(next, not r):
                    return False
            return True

        for i in range(n):
            if br[i] is None:
                if not f(i, True):
                    return False
        return True
